package com.zzz.sort.merge;

import java.util.Arrays;

/**
 * 归并排序
 *
 * @author zizan
 */
public class MergeSort {

    // 归并排序需要一个辅助数组，用来进行分段数组合并
    public static int[] auxiliary;

    public static void main(String[] args) {
        int[] array = new int[]{5, 1, 7, 4, 2, 7, 3, 1, 9};
        auxiliary = new int[array.length];
        sort(array);
        System.out.println(Arrays.toString(array));
    }

    public static void sort(int[] array) {
        // 需要一个相同的数组空间进行 比较交换
        sort(array, 0, array.length - 1);
    }

    public static void sort(int[] array, int low, int high) {

        // 当拆分到只有一个元素的时候，直接返回，因为无法拆分成两段
        if (low >= high) {
            return;
        }

        // 将数组分成两段
        int mid = (high + low) / 2;

        // 将左边的排好序
        sort(array, low, mid);

        // 将右边的排好序
        sort(array, mid + 1, high);

        // 将左边和右边进行合并
        merge(array, low, mid, high);
    }

    // 将两段各自已有序的数组合并在一起
    public static void merge(int[] array, int low, int mid, int high) {
        // 如果这段只有两个元素的话，直接判断大小然后交换就返回了
        if (low == mid && array[low] > array[high]) {
            auxiliary[low] = array[low];
            array[low] = array[high];
            array[high] = auxiliary[low];
            return;
        }

        // 如果第二段最小值比第一段最大值要大，那么就无需一一比较
        if (array[mid] < array[mid + 1]) {
            return;
        }
        // 将low - high的元素复制到辅助数组对应的位置上
        if (high + 1 - low >= 0) System.arraycopy(array, low, auxiliary, low, high + 1 - low);

        int firstIndex = low, m = mid + 1;

        /*
           然后一一两个分段一一比较，放入原数组中
           第一段 [1, 4, 7]
           第二段 [2, 5, 6]
           合并成 [1, 2, 4, 5, 6]
         */
        while (low <= high) {
            if (firstIndex > mid) {
                array[low++] = auxiliary[m++];
            } else if (m > high) {
                array[low++] = auxiliary[firstIndex++];
            } else if (auxiliary[firstIndex] < auxiliary[m]) {
                array[low++] = auxiliary[firstIndex++];
            } else {
                array[low++] = auxiliary[m++];
            }
        }
    }
}
